1. Field of the Invention
This invention generally relates to design verification, and more specifically relates to test program generation in a context of a computer mechanism and methods for testing a design for compliance with the design specification.
2. Description of the Related Art
An important aspect of designing a hardware or software design, for example an advanced computer processor, is the ability to test the design of the processor thoroughly, in order to assure that the design complies with desired architectural, performance and design specifications. In current industrial practice, most of the verification is done by generating a very large number of tests by random test generators.
Test program generators are basically sophisticated software engines, which are used to create numerous test cases. By appropriate configuration, it is possible for test generation to be focused on very specific ranges of conditions, or broadened to cover a wide range of logic. Today, large numbers of test cases can be created automatically in the time that a single test case could be written manually, as was done prior to the advent of test case generators. Modern test program generators are sophisticated enough to evaluate the microarchitectural implementation of a processor.
Typically, the input to the test program generator is a user-defined sequence of partially specified instructions, known as an instruction stream, which acts as a template for the test to be generated. The instruction stream is generally incomplete, in that various details of each instruction, such as the specific source and the target resources to be used, the data values of each uninitialized resource, and even the exact instruction to be generated, may be left unspecified. The test program generator then generates a complete test by filling in the missing information with random values. The choice of random values is often biased, so as to increase the likelihood of detecting a design flaw. The use of templates in this manner allows the creation of numerous test cases that stress the implementation of the logic, creating various conditions such as “buffer full”, or “pipe stall”.
An example of a conventional test program generator is the IBM tool, Genesys, which is disclosed in the document Model-Based Test Generation for Process Design Verification, Y. Lichtenstein et. al., Sixth Innovative Applications of Artificial Intelligence Conference, August 1994, pp. 83–94. An updated version, of Genesys, known as Genesys-Pro, is a generic random test generator, targeted at the architectural level and applicable to any architecture.
Another conventional test program generator, AVPGEN, is disclosed in the document AVPGEN—A Generator for Architecture Verification Test Cases, A. Chandra, et al., IEEE Trans. Very Large Scale Integration (VLSI) Syst. 3, No. 2, pp. 188–200 (June 1995).
Still another test generator is disclosed in the publication B. O'Krafka, et al., MPTG: A Portable Test Generator for Cache-Coherent Multiprocessors, International Conference on Computers and Communications, 1995, pp. 38–44. This generator is capable of generating tests that include scenarios with unpredictable results and relies on checks carried out for intermediate points in the test.
The principles of the present invention may be applied to any of the above-noted test generators, as well as other test pattern generation tools, such as the verification automation tool SpecMan™ available from Verisity™ , 2041 Landings Drive, Mountain View, Calif. 94043 and the Vera Testbench Automation product, available from Synopsys, Inc. 700 East Middlefield Road, Mountain View, Calif. 94043. A method previously used to increase the capability of test generators examines the state of the design before generating the next input. In this method, often referred to as dynamic generation, the test generator uses the state of the design to determine inputs having the best chances of producing an interesting test case. For example, if the goal of the test generator is to create resource interdependency in the pipelines of a processor, it generates instructions that use the same resources as the instructions already in the pipelines.
An alternative approach to improve coverage uses symbolic simulation and symbolic trajectory evaluation techniques. These techniques are described, respectively, in the documents Improving Coverage Analysis and Test Generation for Large Designs, J. Bergmann and M. Horowitz, Proceedings of the International Conference on Computer Design, pp. 580–583, November 1999, and Formal verification by Symbolic Evaluation of Partially-ordered Trajectories, C. J. H. Seger and R. E. Bryant, Formal Methods in System Design: An International Journal, 6(2): 147–189, March 1995. In symbolic simulation, some of the inputs to the design are represented as symbols. These symbols propagate through the circuit to the outputs. The main advantage of symbolic simulation is that large spaces can be covered in parallel, with a single symbolic input. However, this technique still suffers from explosion of the symbol representation, and thus it is limited to small designs. In addition, it is difficult for symbolic simulators to simulate complex functions and operators, such as multiplication.
A third approach builds test generators that include a precise model of the verified designs. Using this model, the test generator represents a desired event as a state-machine traversal problem or a constraint satisfaction problem. A solution of this problem yields a test case in which the desired event occurs. The main disadvantage of this approach is that it requires considerable effort to specify of the model and build the generation engine.
The use of such advanced random test generators may increase the quality of generated tests, but cannot ensure that all the “dark corners” in the design are exposed, and that the entire design is adequately exercised. The term dark corners as used herein with respect to the design refers to events that are difficult to anticipate in practice, and for which test cases are difficult to construct using test generators. Typical dark corners include transient interdependencies of resources of a processor. Coverage analysis helps detect non-covered events, but does not help cover these events. Generation of interesting test cases that reach these difficult-to-cover dark corners is one of the main challenges in functional design verification.
In the case of software designs, the main problem in testing concurrent programs is their nondeterminism: two executions of such a program may yield different results. Most of the work in the field of concurrent testing has been focused on detecting race conditions. However, race conditions have a low probability of manifesting themselves, and even when they do it is not always an indication of a fault.
One approach to testing software designs is disclosed in the documents O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur., Multithreaded Java Program Test Generation. IBM Systems Journal, 41(1):111–125, 2002, and S. D. Stoller. Model-checking Multi-threaded Distributed Java Programs, in Proceedings of the 7th International SPIN Workshop on Model Checking of Software, pages 224–244, New York, 2000. Springer Verlag. The problem of generating different interleaving for the purpose of revealing concurrent faults was approached by seeding the program with conditional sleep statements at shared memory access and synchronization events. At run time, random, biased random, or coverage-based decisions were taken as to whether to execute seeded primitives.